package com.zhouxianglh.p33;

/**
 * 33. 搜索旋转排序数组
 * <p>
 * 二分法的运用
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        /*
         System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
         System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
         System.out.println(search(new int[]{4, 2}, 3));
         System.out.println(search(new int[]{1, 3}, 0));
        */
        System.out.println(search(new int[]{3, 1}, 4));
    }

    public static int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (true) {
            if (nums[left] == target) {
                return left;
            }
            if (nums[right] == target) {
                return right;
            }
            //
            if (left == right || left > right) {
                return -1;
            }
            //
            if (nums[left] > target && nums[right] < target) {
                return -1;
            }
            //二分法
            if (nums[left] > nums[left + 1] || nums[right] < nums[right - 1]) {
                if (nums[left + 1] == target) {
                    return left + 1;
                }
                if (nums[right - 1] == target) {
                    return right - 1;
                }
                if ((left + 1) == (right - 1) || (left + 1) > right - 1) {
                    return -1;
                }
                int low = left + 1;
                int high = right - 1;
                while (low <= high) {
                    int mid = (low + high) >>> 1;
                    int midVal = nums[mid];

                    if (midVal < target) {
                        low = mid + 1;
                    } else if (midVal > target) {
                        high = mid - 1;
                    } else {
                        return mid;
                    }
                }
                return -1;
            }
            //
            left++;
            right--;
        }
    }
}
